package 牛客算法篇;

/**
 * Created with IntelliJ IEDA.
 * Description:
 * User:86186
 * Date:2024-03-09
 * Time:9:16
 */

import java.util.PriorityQueue;

/**
 *
 牛客算法篇:BM47 寻找第K大
 有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。
 给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。
 要求：时间复杂度 O(nlogn)O(nlogn)，空间复杂度 O(1)O(1)
 数据范围：0≤n≤10000≤n≤1000， 1≤K≤n1≤K≤n，数组中每个元素满足 0≤val≤100000000≤val≤10000000
 示例1
 输入：
 [1,3,5,2,2],5,3
 返回值：
 2
 */
public class findKth {
    public static void main(String[] args) {
        System.out.println(findKth(new int[]{1, 3, 5, 2, 2}, 5, 3));
    }
    public static int findKth(int[] a, int n, int k) {
        if (n < k || k == 0) {
            return -1;
        }
        quickSort(a, 0, n - 1);
            return a[n - k];
    }

    public static void quickSort(int[] a, int start, int end) {
        int low = start;
        int high = end;
        int reference = a[start];
        if (low >= high) {
            return;
        }
        while (low < high) {
            while (a[low] <= reference && low < end) {
                low++;
            }
            while (a[high] >= reference && high > start) {
                high--;
            }
            if (low < high) {
                swap(a, low, high);
            }
        }
        swap(a, start, high);
        quickSort(a, start, high - 1);
        quickSort(a, high + 1, end);
    }

    public static void swap(int[] a, int low, int high) {
        int temp = a[low];
        a[low] = a[high];
        a[high] = temp;
    }
}
